/*提交链接：https://leetcode.cn/problems/longest-increasing-subsequence/
  300.最长递增子序列
  刘思琪 2024/9/7
*/

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int l=nums.size();
        vector<int>dp(l,1);  //每一个数据都是一个子序列
        int ans=1;
        for(int i=0;i<l;i++){          //记录以第i的数据结尾的最大递增子序列
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){    //说明可以将nums[i]放入以j结尾的序列里面，此时对应的dp增加         
                    dp[i]=max(dp[i],dp[j]+1);      //对以i结尾的数据进行更新
                    ans=max(ans,dp[i]);
                }
            }
        }
        return ans;
    }
};